import java.util.Arrays;
import java.util.Comparator;

/**
 * @program: leetcode056
 * @author: JCM
 * @create: 2023-03-06 11:14
 * @description:
 **/
public class Main {
    public static void main(String[] args) {
        int[][] arr = {{3,4},{4,5},{6,7},{1,10}};
        int l = arr.length;// 记录原数组长度
        int[][] ans = new int[l][2];// 保存遍历结果
        int index = 0;// 记录 ans 下标以及 长度
        // 重新compare方法可以大大提高排序效率
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        // 将元素组进行排序排序，应对类似 {1,10}这样的区间
        // 冒泡排序时间复杂度较高
//        for (int i = 0; i < l-1; i++) {
//            for(int j = 0; j < l-i-1; j++) {
//                if(arr[j][0] > arr[j+1][0]) {
//                    int tmp = arr[j][0];
//                    arr[j][0] = arr[j+1][0];
//                    arr[j+1][0] = tmp;
//                    tmp = arr[j][1];
//                    arr[j][1] = arr[j+1][1];
//                    arr[j+1][1] = tmp;
//                }
//            }
//        }
        for (int i = 0; i < l; i++) {
            System.out.println(arr[i][0]+" "+arr[i][1]);
        }
        // 将第一个区间存到 ans
        ans[0][0] = arr[0][0];
        ans[0][1] = arr[0][1];
        // 遍历原数组
        for (int i = 1; i < l; i++) {
            boolean flg = false;
            for(int j = ans[index][1]; j >= ans[index][0]; j--) {
                // 找到有交集的区间，给 ans 的区间更新
                if(j >= arr[i][0] && j <= arr[i][1]) {
                    ans[index][0] = Math.min(arr[i][0],ans[index][0]);
                    ans[index][1] = Math.max(arr[i][1],ans[index][1]);
                    flg = !flg;
                    break;
                }
            }
            // 两个区间没有关系时，将当前区间存入 ans 即可
            if (!flg) {
                index++;
                ans[index][0] = arr[i][0];
                ans[index][1] = arr[i][1];
            }
        }
        // 我们在遍历之前已经存了一个数据，所以在这里需要给 index加一，如果不加一的话，我们的数组长度就会少一个
        index++;
        int[][] res = new int[index][2];
        for (int i = 0; i < index; i++) {
            for (int j = 0; j < 2; j++) {
                res[i][j] = ans[i][j];
                System.out.print(res[i][j]+" ");
            }
            System.out.println();
        }


    }
}
